//地下城游戏
//测试链接：https://leetcode.cn/problems/dungeon-game/
public class CalculateMinimumHP {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length, n = dungeon[0].length;
        int[][] dp = new int[m+1][n+1]; //dp表表示dp[i][j]到右下角需要的健康点数
        //初始化dp
        for(int i = 0;i <= n; i++) dp[m][i] = Integer.MAX_VALUE;
        for(int i = 0;i <= m; i++) dp[i][n] = Integer.MAX_VALUE;
        if(dungeon[m-1][n-1] <= 0) dp[m-1][n-1] = -dungeon[m-1][n-1]+1;
        else dp[m-1][n-1] = 1;

        for(int i = m-1; i >= 0; i--) {
            for(int j = n-1; j >= 0; j--) {
                if(i == m-1 && j == n-1) continue;

                int min = Math.min(dp[i+1][j], dp[i][j+1]);
                if(dungeon[i][j] - min >= 0) {
                    dp[i][j] = 1;
                }else {
                    dp[i][j] = -(dungeon[i][j] - min);
                }
            }
        }

        return dp[0][0];
    }
}
